剑指Offer题解 - Day69

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

分析：

首先考虑使用暴力法求解。思路是进行双层遍历，然后判断外层的值大于内层的值时，累加器递增，最终返回累加器变量即可。

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i; j < nums.length; j++) {
            if (nums[i] > nums[j]) count++;
        }
    }
    return count;
};

该方法浅显易懂，但是由于数组长度最大是50000，因此该方法会超时，本题不适合采用双层遍历。

那么如何降低时间复杂度呢？最好是一次遍历就可以找出所有的逆序对。

归并排序

可以借用归并的思想进行题解。当进行合并的时候，可以通过判断左右子数组内元素的大小关系，来统计最终的逆序对个数。

具体代码如下：

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    const length = nums.length;
    let temp = Array.from({ length }); // 临时数组，存储合并时候的左右子数组
    const mergeSort = (l, r) => {
        if (l >= r) return 0;  // 单个元素，递归终止
        let m = Math.floor((l + r) / 2); // 寻找中间元素，进行划分
        let res = mergeSort(l, m) + mergeSort(m + 1, r); // 继续拆分左右子数组

        // 合并阶段
        let i = l; // 左子数组的首位元素索引
        let j = m + 1; // 右子数组的首位元素索引
        for (let k = l; k <= r; k++) {
            temp[k] = nums[k]; // 将左右子数组的元素缓存起来
        }
        for (let k = l; k <= r; k++) { // 将较小元素按顺序放入原数组相对位置
            if (i === m + 1) nums[k] = temp[j++];
            else if (j === r + 1 || temp[i] <= temp[j]) nums[k] = temp[i++];
            else {
                nums[k] = temp[j++];
                res += m - i + 1;
            }
        }
        return res;
    }
    return mergeSort(0, length - 1);
};

• 时间复杂度 O(nlogn)。
• 空间复杂度 O(n)。

分析：

具体的代码逻辑，注释里已经写得很清楚了。具体来看第二次循环的相关逻辑。

这里主要是合并阶段，将左右子数组的元素进行逐个比较，哪个元素小就将元素放入原数组指定位置。这也告诉我们，归并排序是原地排序。

如果左子数组的索引超出了左子数组，意味着左子数组的元素已经排序到原数组中了，这时只需要将右子数组的元素逐个放入原数组即可。同理，当右子树组的索引超出了右子树组，只需要将左子数组的元素逐个放入原数组即可。

如果左子数组的元素小于等于右子树组的元素，将左子树组的元素放入原数组。否则，意味着左边大右边小，这时就需要右子树组的元素放入原数组。此时就符合前面元素大于后面元素，可以形成逆序对。

而当前状态下逆序对的个数为m - i + 1 。具体是怎么算出来的呢？是因为左子数组此时是有序的，右子树组此时也是有序的，如果说当前左边大于右边，也就是说，在左子数组中，当前元素及以后所有的元素都会大于右边的当前元素。因此需要将右子树组的首位索引减去当前左元素的索引。

当前递归需要返回最终累加的res结果。这样可以在回溯时不断进行累加，最终得到所有的逆序对。

总结

本题采用归并排序的方法求得逆序对的个数。难度系数困难。核心逻辑在于合并时计算逆序对的个数。

归并排序的时间复杂度是O(nlogn) ，而维护临时数组需要占用O(n) 的空间。